package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;
import com.sun.jmx.remote.internal.ArrayQueue;

/*
513.找树左下角的值
 */
public class Of20210312LeetCode513 {
    /*
    给定一个二叉树，在树的最后一行找到最左边的值。
     */
    public static void main(String[] args) {
        System.out.println(findBottomLeftValue(new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15),
                new TreeNode(7)))));
    }

    /*
    递归
     */
    private static int maxLen = Integer.MIN_VALUE; //控制深度
    private static int maxLeftValue;

    private static void traversal(TreeNode root, int leftLen) {
        if (root.left == null && root.right == null) {
            if (leftLen > maxLen) {
                maxLen = leftLen;
                maxLeftValue = root.val;
            }
            return;
        }
        if (root.left != null) {
            traversal(root.left, leftLen + 1); // 隐藏着回溯
        }
        if (root.right != null) {
            traversal(root.right, leftLen + 1); // 隐藏着回溯
        }
        return;
    }

    private static int findBottomLeftValue(TreeNode root) {
        traversal(root, 0);
        return maxLeftValue;
    }

    /*
    迭代
     */
    private static int findBottomLeftValue2(TreeNode root) {
        if (root == null) return 0;
        ArrayQueue<TreeNode> queue = new ArrayQueue<>(10);
        int result = 0;
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove(0);
                if (i == 0) result = node.val; // 记录最后一行第一个元素
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return result;
    }
}
